El Problema de Minimización

• Puede haber más de un AFD que acepte el mismo lenguaje.
• Entre esos AFD equivalentes, es a menudo útil encontrar el más pequeño, es decir, el AFD con el menor número de estados.
• Esto es especialmente importante cuando se usan AFDs para diseñar circuitos digitales, o para crear analizadores léxicos.

Estados No Alcanzables

• A veces un DFA contiene estados que no pueden ser alcanzados desde el estado inicial.
• Esos estados son fáciles de identificar y pueden ser eliminados sin cambiar el lenguaje aceptado por el DFA.
• El estado 5 no es alcanzable y puede ser eliminado sin alterar el lenguaje aceptado por el DFA.

Estados Equivalentes o Indistinguibles

• Dos estados son equivalentes si el unirlos en uno no altera el lenguaje aceptado por el DFA.
• Unir estados equivalentes es otra forma de simplificar un DFA sin alterar el lenguaje que acepta.
• Dos estados q y r de un autómata M son indistinguibles (escrito q ≡ r) si el autómata que se obtiene de M al hacer q el estado inicial es equivalente al obtenido haciendo r el estado inicial.
• La relación ≡ es una equivalencia (reflexiva, simétrica, y transitiva) y divide el conjunto de estados de un autómata en clases de equivalencia.
• Cada clase de equivalencia corresponde a un estado en el AFD mínimo.

Detectando la Equivalencia

• Para cualquier par de estados q y r, decimos que q ≡_n r significa que esos estados no son distinguibles por ninguna cadena de longitud menor o igual a n.
• Dos estados q y r son n-distinguibles si con una cadena de longitud menor o igual a n se llega a un estado final partiendo de q, pero no de partiendo de r, o viceversa.
• Podemos relacionar ≡_n con ≡_n-1 como sigue: para cualquier par de estados q y r, y un entero n > 0, q ≡_n r si y solo si:

1. q ≡_n-1 r, y
2. ∀ a ∈ Σ, δ(q,a) ≡_n-1 δ(r,a)

Algoritmo de Minimización

1. Eliminar todos los estados no alcanzables.
2. Las clases de equivalencias ≡₀ son F (el conjunto de estados finales) y Q-F (los estados no finales).
3. Calcular las clases de equivalencia ≡_n a partir de las de ≡_n-1
4. Repetir 3 hasta que ≡_n sea idéntico a ≡_n-1.
5. Cada clase de equivalencia resultante corresponde un estado del AFD mínimo.
6. Los estados finales en el AFD mínimo son las clases que contengan estados finales del AFD original.
7. El estado inicial el AFD mínimo es la clase de equivalencia que contenga al estado inicial del AFD original.
8. La tabla de transiciones del AFD mínimo se calcula a partir de la tabla original.
   1. Para cada entrada δ(q_i,a) = q_j en la tabla original, se coloca una entrada δ'(C(q_i),a) = C(q_j) en la tabla del AFD mínimo, donde C(q) es la clase de equivalencia del estado q.

Ejemplos

Ejemplo del libro

Tabla de transiciones δ

Búsqueda de estados equivalentes:

Nueva tabla de transiciones:

afd_para_minimizar.png (image/png)
afd_para_minimizar.png (image/png)
afd_minimizado.png (image/png)